/**
 * 项目名称: Dijkstra.cpp
 * 项目路径: study/DataStructure/数据结构/图/应用/最短路径
 * 编辑时间: 2024年08月12日08时48分23秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * Dijkstra算法:Dijkstra用来找两点之间的最短路径,
 * 两点之间经过若干个点,
 * 最短路径是基于前一个点的路径也是最短的,
 * 更新点时需要加上前面的路径
 */

const int N = 100010;
int g[N][N];//存储每条边
int dist[N];//存储1号点到每个点的最短距离
bool st[N];//存储每个点的最短路是否已经确定

/**
 * 求1号点到n号点的最短路,如果不存在则返回-1
 * @param n 顶点数
 * @return
 */
int dijkstra(int n){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i =0;i<n-1;i++){
        int t = -1;
        for(int j =1;j<=n;j++)//在还未确定最短路的点中,寻找距离最小的点
            if(!st[j] && (t==-1)||dist[t]>dist[j])
                t=j;

        // 用t更新其他点的距离
        for(int j =1;j<=n;j++)
            dist[j]= min(dist[j],dist[t]+g[t][j]);

        st[t]= true;
    }

    if(dist[n] == 0x3f3f3f3f)return -1;
    return dist[n];
}
int main() {

    return 0;
}
